package com.heima.leetcode.practice;

import java.util.HashMap;

/**
 * leetcode 146 LRU缓存机制
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/19 11:30
 */
public class E146 {

    /**
     * LRU缓存类，LRU就是指最久未使用
     */
    public static class LRUCache {

        private final HashMap<Integer, CacheNode> caches; // 因为要O(1)的时间复杂度去获取、删除、更新元素（缓存项），键是缓存项的key，值是缓存项

        private final DoublyLinkedList lruList; // 双向链表，越在右边的节点越久未使用，节点就是缓存项

        private final int capacity; // 缓存的总容量

        /**
         * 构造器初始化
         * @param capacity 缓存总容量
         */
        public LRUCache(int capacity) {
            this.caches = new HashMap<>();
            this.lruList = new DoublyLinkedList();
            this.capacity = capacity;
        }

        /**
         * 双向链表缓存项节点类
         */
        static class CacheNode {
            CacheNode prev; // 前一个节点
            CacheNode next; // 后一个节点
            int key; // 键
            int value; // 值

            /**
             * 无参构造
             */
            public CacheNode() {
            }

            /**
             * 有参构造
             * @param key 键
             * @param value 值
             */
            public CacheNode(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }

        /**
         * 双向链表类
         */
        static class DoublyLinkedList{
            CacheNode head; // 头指针
            CacheNode tail; // 尾指针
            int size; // 大小

            /**
             * 无参构造
             */
            public DoublyLinkedList() {
                this.head = new CacheNode();
                this.tail = new CacheNode();
                head.next = tail;
                tail.prev = head;
            }

            /**
             * 头部添加缓存项
             * @param node 缓存项
             */
            public void addFirst(CacheNode node){
                CacheNode next = head.next;
                CacheNode prev = head;
                node.next = next;
                next.prev = node;
                node.prev = prev;
                prev.next = node;
                size++;
            }

            /**
             * 移除指定缓存项
             * @param node 缓存项
             */
            public void remove(CacheNode node){
                CacheNode prev = node.prev;
                CacheNode next = node.next;
                prev.next = next;
                next.prev = prev;
                size--;
            }

            /**
             * 移除尾部缓存项
             * @return 移除的缓存项
             */
            public CacheNode removeLast(){
                CacheNode last = tail.prev;
                remove(last);
                return last;
            }
        }

        /**
         * 根据key获取缓存项
         * @param key 键
         * @return 缓存项
         */
        public int get(int key) {
            CacheNode node = caches.get(key);
            // 1. 该缓存项不存在
            if (node == null){
                return -1;
            }
            // 2. 该缓存项存在
            else {
                // 2.1 移除该缓存项
                lruList.remove(node);
                // 2.2 将该缓存项加到链表头部，表示最新被使用
                lruList.addFirst(node);
                return node.value;
            }
        }

        /**
         * 新增或者更新缓存项
         * @param key 键
         * @param value 值
         */
        public void put(int key, int value) {
            CacheNode node = caches.get(key);
            // 1. 存在该键为key的缓存项，则更新
            if (node != null){
                node.value = value;
                // 1.1 移除当前缓存项
                lruList.remove(node);
                // 1.1 将该缓存项加到链表头部，表示最新被使用
                lruList.addFirst(node);
            }
            // 2. 不存在键为key的缓存项，则新增
            else {
                CacheNode newNode = new CacheNode(key, value);
                // 2.1 向缓存数据中新增这一条缓存项
                caches.put(key, newNode);
                // 2.2 将该缓存项加到链表头部，表示最新被使用
                lruList.addFirst(newNode);
                // 2.3 检查新增后是否超出容量限制
                if (lruList.size > capacity){
                    // 超出容量限制则淘汰最久未使用的缓存项
                    CacheNode last = lruList.removeLast();
                    caches.remove(last.key);
                }
            }
        }
    }
}
